


// 排列
// function fun(nums) {
//     let result = []
//     const dfs = (arr) => {
//         if(arr.length == nums.length) {
//             result.push([...arr])
//             return
//         }

//         nums.forEach(item => {
//             if(arr.indexOf(item) == -1) {
//                 dfs([item, ...arr])
//             }
//         })
//     }
//     dfs([])
//     return result
// }

// console.log(fun([1,2,3,4]))

// // 组合总和
// function arrSum(nums, target) {
//     let result = []
//     const dfs = (target, arr, i) => {
//         if(target == 0) {
//             result.push([...arr])
//             return
//         }
//         if(target < 0) {
//             return
//         }
        
//         for(let j = i; j < nums.length; j++) {
//             arr.push(nums[j])
//             dfs(target - nums[j], arr, j)
//             arr.pop()
//         }
//     }
//     dfs(target, [], 0)
//     return result
// }

// console.log(arrSum([1,1,2,3,5], 5));


// 判断回文

function isHuiwen(str) {
    for(let i = str.length - 1, j = 0; i >= 0, j < str.length; i--, j++) {
        if(str[i] !== str[j]) {
            return false
        }
    }
    return true
    
}
console.log(isHuiwen('aaabbaaa'));


function ListNode(value) {
    this.value = value
    this.next = null
}

let a = new ListNode(3)
a.next = new ListNode(4)
a.next.next = new ListNode(5)

// 反转链表
function reverse(head) {
    let dummy = null
    while(head) {
        let temp = head.next
        head.next = dummy
        dummy = head
        head = temp
    }
    // return dummy
console.log(dummy);

}


reverse(a)

// 递归反转链表
function reverse2(head) {
    if(head == null || head.next == null) {
        return head
    }
    const newHead = reverse2(head.next)
    head.next.next = head
    head.next = null
    return newHead
}
console.log(reverse2(a));


// 节流

function debouce(fun, time) {
    let old = 0
    return function () {
        let newTime = Date.now()
        let value = newTime - old
        if(value > time) {
        fun()
        old = newTime
        }
    }
}

// 防抖

function defance(fun, time) {
    let timer
    return function() {
        clearTimeout(timer)
        timer = setTimeout(fun, time)
    }
}



// call的实现

let obj = {
    'a':1,
    'b':2
}

function test() {
    console.log();
}


// 树

function ListTree(value) {
    this.value = value
    this.left = null
    this.left = null
}

let a = new ListTree('a')
a.left = new ListTree('b')
a.right = new ListTree('c')
a.left.left = new ListTree('d')
a.right.right = new ListTree('e')

// 前序遍历

// let res = []
// function traversal(tree) {
//     if(!tree) return
//     res.push(tree.value)
//     traversal(tree.left)
//     traversal(tree.right)
// }

// traversal(a)

// console.log(res);


// 中序遍历
let res1 = []
function MidTraversal(tree) {
    if(!tree) return
    MidTraversal(tree.left)
    res1.push(tree.value)
    MidTraversal(tree.right)
}

MidTraversal(a)
console.log(a);

// 后序遍历
let res2 = []
function dfs(tree) {
    if(!tree) return
    dfs(tree.left)
    dfs(tree.right)
    res2.push(tree.value)
}
dfs(a)
console.log(res2);

// 树的查找


// 树的删除


// 树的添加